package src.dp.easy;

import java.util.Arrays;

public class no152 {//乘积最大子数组

    /**
     * dp[i][j]含义：以 i 结尾的子数组最大乘积为dp[i]
     * 递推公式：
     * maxdp[i] = Math.max(maxdp[i-1]*nums[i], Math.max(nums[i], mindp[i-1]*nums[i]) );
     * mindp[i] = Math.min(mindp[i-1]*nums[i], Math.min(nums[i], maxdp[i-1]*nums[i]) );
     * 初始化：dp[i] = nums[i]
     * 遍历顺序：从左往右
     */
    public static void main(String[] args) {
        int[] arr = {2,3,-2,4};
        System.out.println(maxProduct(arr));
    }

    public static int maxProduct(int[] nums) {
        if (nums.length == 1) return nums[0];
        int max = nums[0];
        int[] maxdp = new int[nums.length];
        int[] mindp = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            maxdp[i] = nums[i];
            mindp[i] = nums[i];
        }
        for (int i = 1; i < nums.length; i++) {

            maxdp[i] = Math.max(maxdp[i-1]*nums[i], Math.max(nums[i], mindp[i-1]*nums[i]) );
            mindp[i] = Math.min(mindp[i-1]*nums[i], Math.min(nums[i], maxdp[i-1]*nums[i]) );
            max = Math.max(max, Math.max(maxdp[i], mindp[i]));

        }
        System.out.println(Arrays.toString(maxdp));
        return max;

    }


    /**
     * dp状态压缩，只用一个变量存当前的最大值和最小值
     * 令imax为当前最大值，则当前最大值为 imax = max(imax * nums[i], nums[i])
     * 由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值
     * imin，imin = min(imin * nums[i], nums[i])
     * 当负数出现时则imax与imin进行交换再进行下一步计算
     */
    public int maxProduct2(int[] nums) {
        int max = nums[0];
        int imax = 1, imin = 1;  //当前最大值和最小值
        for (int num : nums) {
            //当前元素是负数时，交换imax、imin
            if (num < 0) {
                int temp = imax;
                imax = imin;
                imin = temp;
            }
            imax = Math.max(imax * num, num);
            imin = Math.min(imin * num, num);

            max = Math.max(max, imax);
        }
        return max;
    }

}
